% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{ulem}
\newcounter{task}
\newcommand{\task}{\stepcounter{task}\paragraph{Task \thetask~--~Solution\\}}

\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large 5. Problem Session -- Solution\\ \vspace{0.2em}
        {\bf Secure Channels}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo \\
       \vspace{0.2em} \firstnamethree \lastnamethree\\
        \vspace{0.2em} \matriculationnumberthree
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}

\newcommand{\firstnamethree}{Naveeni	}
\newcommand{\lastnamethree}{ Kumar Goswam}
\newcommand{\matriculationnumberthree}{113967}

\begin{document}
\pagestyle{plain}
\header


% number of tasks are automatically generated

\task

a) $h_{a}(x)$ = (ax mod p) mod N, where $p \in \mathbb{P}$ , p > N, $a \in \left\{ 0, ... , p -1\right\}$\\
$h_a(m_1)$ = $h_a(m_2)$ $\Leftrightarrow$ \\
(a$m_1$ mod p) mod N = (a$m_2$ mod p) mod N $\Leftrightarrow$\\
((a$m_1$ mod p) - (a$m_2$ mod p) = 0) mod N $\Leftrightarrow$ \\
(a$m_1$ mod p) - (a$m_2$ mod p) $\in$ $\left\{ -\lfloor{{p - 1} \over N}\rfloor N,...,-2N, -N, 0, N, 2N,...,\lfloor {{p - 1} \over N}\rfloor N  \right\}$ $\Leftrightarrow$\\
by adding p to every negative reminder move range to $\left\{0, ..., p - 1 \right\}$\\
a($m_1$ - $m_2$) mod p $\in$ R =  $\left\{ 0, N, 2N,..., \lfloor{{p - 1} \over N}\rfloor N , p - N, p - 2N, ...., p -  \lfloor{{p - 1} \over N}\rfloor N \right\}$ $\Leftrightarrow$\\
since $Z_p$ is a field ($p \in \mathbb{P}$)  and $m_1$ $\ne$ $m_2$ there exists inverse of $(m_1 - m_2)$\\
a $\in$ R${(m_1 - m_2)}^{-1}$\\
There are p choices for a,  |R${(m_1 - m_2)}^{-1}$| causes the collision, thus \\
Pr[$h_a(m_1)$ = $h_a(m_2)$] = Pr[a $\in$ R${(m_1 - m_2)}^{-1}$] = $ {|R{(m_1 - m_2)}^{-1}|} \over {p}$ =  $ {|R|} \over {p}$ $\le$ ${ {{2p} \over{N}} \over {p}}$ = ${2 \over N}$\\\\
b) Suppose a $\ne$ 0 and all other conditions hold. Then\\
a$m_1$ + a$m_2$ = iN mod p\\
a($m_1$ - $m_2$) = iN mod p\\
a = iN$(m_1  - m_2)^{-1}$ mod p\\\\
Since a $\ne$ 0 $\exists$ ! a, such as (a$m_1$ mod p) mod N = (a$m_2$ mod p) mod N $\forall m_1, m_2 \in  \left\{ 0, ... , p -1\right\} $\\
We have now p -1 choices for a, $ \lfloor {{p} \over{N}} \rfloor $ choices for i\\
Thus Pr[$h_a(m_1)$ = $h_a(m_2)$] = ${ {{p} \over{N}} \over {p - 1}}$ = (for a large p) = ${1 \over N}$

\task
add a tweak to xor $CMAC_0$\\
make the start value equal $CMAC_0(Nonce) \oplus tweak$,\\
tweak is a random value and change every time, so the result and start value will be random when nonce misuse.\\

\task
a)\\
send (m) to oracle, get C=$(C_0,C_1,C_2)$\\
then using C'=$(C_0,C_1,C_0 \oplus m \oplus const, C_1)$,\\
and C' is always the result of (m,m'), C' will never be rejected by oracle.\\
so the function h=const does not provide AE security.\\
b)\\
send $(m)$ to oracle,get C=$(C_0, C_1, C_2)$\\
then using C'=$(C_0,C_1,C_1 \oplus m, C_1 \oplus m)$,\\
C' is the result of message (m,m')\\
$C_1\oplus m \oplus m \oplus m'=C_1 \oplus m'$\\
C' will never be rejected by oracle.\\
so the function $h=m_1\oplus m_2 ....m_n$ does not provide AE security.\\
\task
For counter mode,\\
send $M_1$\\
$C_1||Y_1=E_k(CV) \oplus M_1||h(M_1)$\\
$M_1||h(M_1)=D_k(C_1||Y_1) = C_1||Y_1 \oplus E_k(CV)$\\
send $M_2$\\
$C_2||Y_2=E_k(CV) \oplus M_2||h(M_2)$\\
$M_2||h(M_2)=D_k(C_2||Y_2) = C_2||Y_2 \oplus E_k(CV)$\\
because $E_k(CV)$ not change,\\
so get $h(M_1) \oplus Y_1= h(M_2) \oplus Y_2 = $part of Ek(CV)\\
then get $Y_2=Y_1 \oplus h(M_1) \oplus h(M_2)$\\ 
$Y_1 \oplus h(M_1)$ is a fixed value for every counter vector, and we can calculate the $Y_i$ by the fixed value xor $h(M_i)$.\\
so we send C'=C||Yi, the oracle will never reject the C', so the function h cannot provide any AE security.\\

\task

$$a) Mac  and  Encrypt: Attack-  Under Chosen Plaintext$$

$$ m= (0,1) ^n $$

Choose Tag function = $$T (E_L(m_0,....m_n-2))$$ Thing to notice here that this tag function is not revealing any information about plaintext and the output tag will appear to be totally random. We can consider this as SUF-CMA-secure MAC

$$Encryption E = E_k(m)$$

$$Final AE scheme = AE(E_k(m)||Tag $$

Now here the one problem with the tag generating scheme is that it is not considering last bits of the messages in other words discarding it so for the  two different messages $$m_0,m_1,....m_i $$ and $$m_0,m_1,....m_j,$$ it will produce the same tag as the scheme doesnt considering last bits of the message for the tag, so these two different messages will be validify at the reciever end and thus resulting in broken AE scheme.  

 
$$ b) Mac then encrypt:  INT-CTXT- $$

Mac then encrypt AE scheme look bit more  secure than  E+M scheme, and it is being used in TLS 1.0. However, it is not fully secure and lot of attack has been made until today on this scheme such as beast and lucky 13. Our attack is influenced by the Poodle attack, which is developed by the google engineers, however their attack purposed to recover get plaintext but we are just carrying out an INT-CTXT, our purpose is that we make the oracle to decrypt the Cipher $ C_i$ and authenticate it which was not decrypted before. 

The attack  take advantage of the fact that the Mac does not include padding( for our scheme, which is also very practical too as it is being for certain applications like TLS)  while generating tag T and padding is necessary for AES secure block cipher for the messages which is not of full  block length . 

The AE scheme look something like this :

$$C_i = E_k( m_i padding( if needed)|| T_l(m_i)$$

Now here the attack is basically man in the middle attack, where the adversary ask the oracle decryption of $ C_i $ and if the tag authentication is valid then the the cipher is turned into plaintext. Thing to be note here is that no matter what cipher adversary provide first it will be decrypted and check for valid padding then it is checked for authentication of tag, which will be denied if the altered cipher provided by the adversary does not turned into a valid tag. 

 Now here lies the trick, generally when adversary will flip the $k_{th}$ bit of cipher and ask oracle for decryption if the flipped bit was by chance were a padding bit then the oracle will deny decryption before checking for the tag authentication. And thus result in little bit quicker denial of decryption on the other hand if the flipped bit was from plain text it will take bit longer as the oracle will deny after checking authentication tag. Noticing this little change of timing between the denial could differ in microseconds and can easily be noticed. Now adversary can check for this change bit by bit and can realize which bit correspond to the padding. which will not take much time. after realizing the padding bit the adversary can flip this bit and ask oracle for decryption. First the oracle will simply decrypt it and the send for authentication, now the padded bits was not used in producing mac so the changed bit in cipher which basically was a padding bit wont effect any change in authentication and will pass authentication check. And now we can conclude that MAC then ENcrypt AE scheme is not INT-CTXT secure. As oracle decrypted the changed cipher $ C_{i'} $

\end{document}
